package cn.bellychang.sword.finger.offer.question051;

/**
 * @author ChangLiang
 * @date 2021/2/19
 */
public class Solution4 {

    private int result = 0;

    public int reversePairs(int[] nums) {

        if (nums.length == 0 || nums.length == 1) {
            return 0;
        }

        int[] target = new int[nums.length];
        mergeSort(0, nums.length - 1, nums, target);
        return result;
    }

    private void mergeSort(int beginIndex, int endIndex, int[] nums, int[] target) {
        if (beginIndex == endIndex) {
            return;
        }
        int middle = beginIndex + ((endIndex - beginIndex) >> 1);
        mergeSort(beginIndex, middle, nums, target);
        mergeSort(middle + 1, endIndex, nums, target);
        merge(beginIndex, middle, endIndex, nums, target);
    }

    private void merge(int beginIndex, int middle, int endIndex, int[] nums, int[] target) {
        int i = beginIndex;
        int j = middle + 1;
        int k = i;
        while (i <= middle && j <= endIndex) {
            if (nums[i] > nums[j]) {
                target[k] = nums[j];
                j++;
                // 注意这里
                result += (middle - i + 1);
            } else {
                target[k] = nums[i];
                i++;
            }
            k++;
        }
        if (i > middle) {
            System.arraycopy(nums, j, target, k, endIndex - j + 1);
        }
        if (j > endIndex) {
            System.arraycopy(nums, i, target, k, middle - i + 1);
        }
        System.arraycopy(target, beginIndex, nums, beginIndex, endIndex - beginIndex + 1);
    }
}
